/*
 * @lc app=leetcode.cn id=25 lang=cpp
 *
 * [25] K 个一组翻转链表
 */

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
   public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        stack<ListNode*> nodeStack;
        ListNode* result = nullptr;  // 保存反转后的整个链表
        ListNode* curNode = head;
        ListNode* prevNode = nullptr;  // 上一组节点的尾部元素
        ListNode* headNode = nullptr;  // 一组节点中的头部元素
        ListNode* tailNode = nullptr;  // 一组节点中的尾部元素

        while (curNode != nullptr) {
            // 将栈中加入最多 k 个节点
            for (int i = 0; i < k; i++) {
                if (i == 0) headNode = curNode;  // 记录每组节点的头部元素
                if (i == (k - 1)) tailNode = curNode;  // 记录每组节点的尾部元素

                nodeStack.push(curNode);
                curNode = curNode->next;

                if (curNode == nullptr) break;
            }

            if (nodeStack.size() < k) {
                // 栈中元素数量小于 k，栈中元素不用反转
                if (prevNode != nullptr) prevNode->next = headNode;
                if (result == nullptr) result = headNode;  // 当前是第一组元素
            } else {
                // 栈中元素数量等于 k，反转栈中的 k 个节点
                ListNode* tmpNode = nullptr;
                ListNode* lastNode = nullptr;
                while (!nodeStack.empty()) {
                    tmpNode = nodeStack.top();
                    nodeStack.pop();

                    if (lastNode != nullptr) {
                        lastNode->next = tmpNode;
                    }
                    lastNode = tmpNode;
                }

                if (prevNode != nullptr) prevNode->next = tailNode;
                prevNode = headNode;
                prevNode->next = nullptr;
                if (result == nullptr) result = tailNode;  // 当前是第一组元素
            }
        }

        return result;
    }
};
// @lc code=end
